【题解】 [JSOI2016]灯塔 决策单调性&DP loj2074 | Qiuly's blog!

【题解】 [JSOI2016]灯塔 决策单调性&DP loj2074

Posted on | Edited on | In | Comments:

其实这道题是 $\rm{POI}$ 的原题，$loj$ 传送门链接：在这呢o(￣︶￣)o

刚开始肯定还是看不出这题是什么 $\rm{DP}$ ，感觉很诡异，但是推一推自然就出来了：

设 $f_i$ 表示 $i$ 的 $p$ 值，那么继续：

发现绝对值很烦人，将绝对值拆开。

原序列翻转一下就可以直接计算后面的式子，也就是说我们只需要考虑第一个：

假设对于 $i$ 来说 $j$ 是最优的决策，那么如果存在一个小于 $j$ 的 $k$ ，是否在转移一个大于 $i$ 的 $l$ 会更优呢？显然不会，可以知道 $i-k$ 显然是大于 $i-j$ 的，而且根号是增长的越来越慢的。所以如果在 $i$ 时 $k$ 就没有 $j$ 优了，那么在以后所以大于 $i$ 的 $l$ 转移时 $k$ 也不可能比 $j$ 优。

也就是说上面的式子满足决策单调性，那么我们可以 $O(n\log n)$ 愉快求出了。

这里说明两个方法：

  • 1. 单调队列维护三元组，三元组包含 $v$ (决策点 $v$) ，$l$ (决策点 $v$ 作为最优决策点的最左端点) ，$r$ (决策点 $v$ 作为最优决策点的最右端点) ，每一次排除掉最右端点小于 $i$ 的元素(因为该元素已经没用了) ，插入队列的时候去掉完全劣于 $i$ 的，然后对于折中的二分即可。(具体参见诗人小 $\rm{G}$ 的题解) 。
  • 2. 分治计算答案。设 $slove(al,ar,vl,vr)$ 表示在原数组 $al$ 到 $ar$ 这段区间的最优决策点位于 $vl$ 到 $vr$ 区间。我们每一次找到 $al$ 到 $ar$ 的中间点，也就是 $mid$ ，然后在 $vl$ 到 $vr$ 寻找最优的决策点更新 $f_{mid}$ ( $\rm{DP}$ 数组)，设这个最优点为 $g$ 。因为满足决策单调性，$al$ 到 $mid-1$ 的所有点的最优决策点一定在 $vl$ 到 $g$ 之间，右边 $mid+1$ 到 $ar$ 的也同理，就这么分治下去即可。

实际运用中分治的效率不如三元组，但是代码却好写得多，很短，并且调试难度也大大降低，所以最终我选择了分治……分治的具体细节看代码。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=6e5+2;
const int inf=1e9+9;

int n;ll a[N];
long double f1[N],f2[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void solve_f1(int al,int ar,int vl,int vr) {
    if(al>ar) return;
    int mid=(al+ar)>>1,g=0;
    f1[mid]=a[mid];
    for(int i=vl;i<=min(vr,mid);++i) {
        long double calc=a[i]+sqrt(double(mid-i));
        if(calc>f1[mid]) f1[mid]=calc,g=i;
    }
    if(!g) g=mid;f1[mid]-=a[mid];
    solve_f1(al,mid-1,vl,g),solve_f1(mid+1,ar,g,vr);
}

void solve_f2(int al,int ar,int vl,int vr) {
    if(al>ar) return;
    int mid=(al+ar)>>1,g=0;
    f2[mid]=a[mid];
    for(int i=vr;i>=max(vl,mid);--i) {
        long double calc=a[i]+sqrt(double(i-mid));
        if(calc>f2[mid]) f2[mid]=calc,g=i;
    }
    if(!g) g=mid;f2[mid]-=a[mid];
    solve_f2(al,mid-1,vl,g),solve_f2(mid+1,ar,g,vr);
}

int main() {
    IN(n);
    for(int i=1;i<=n;++i) IN(a[i]);
    solve_f1(1,n,1,n),solve_f2(1,n,1,n);
    /*最终没有翻转序列，而是选择做两遍分治*/
    for(int i=1;i<=n;++i)
        printf("%lld\n",(ll)ceil(max(f1[i],f2[i])));
    return 0;
}

本文标题:【题解】 [JSOI2016]灯塔 决策单调性&DP loj2074

文章作者:Qiuly

发布时间:2019年04月30日 - 00:00

最后更新:2019年05月05日 - 09:22

原始链接:http://qiulyblog.github.io/2019/04/30/[题解]loj2047/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。